package 双指针系列;

class ListNode{
    int val;            //当前节点的值
    ListNode next;  //指向下一个节点的指针/引用
    //    ListNode prev;  //指示链表中的上一个节点
    ListNode() {}

    ListNode(int val) {
        this.val = val;
        next = null;
    }

    ListNode(int val,ListNode next) {
        this.val = val;
        this.next = next;
    }
}
public class ReverseList {
    //双指针
    public ListNode reverseList(ListNode head){
        ListNode prev = null;
        ListNode cur = head;
        ListNode temp = null;
        while(cur!=null){
            temp = cur.next;    // 保存下一个节点
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        return null;
    }

    //递归
    public ListNode reverseList1(ListNode head){
        return reverse(null,head);
    }
    private ListNode reverse(ListNode prev,ListNode cur){
        if(cur == null){
            return prev;
        }
        ListNode temp = null;
        temp = cur.next;
        cur.next = prev;

        return reverse(cur,temp);
    }

    ListNode reverseList2(ListNode head) {
        // 边缘条件判断
        if(head == null) return null;
        if (head.next == null) return head;

        // 递归调用，翻转第二个节点开始往后的链表
        ListNode last = reverseList2(head.next);
        // 翻转头节点与第二个节点的指向
        head.next.next = head;
        // 此时的 head 节点为尾节点，next 需要指向 NULL
        head.next = null;
        return last;
    }
}
